import random
from copy import *
import numpy
class optimization_ga(object):
    """This is a standard genetic algorithm that takes in a fitness function that takes in a list of integers, bools, and loating point numbers, each representing a gene.  A corresponding range is also provided for integers and floating point values [low,high). The gene spec is in the form [type,low,high],where low and high are only applicable to integers and floats. There are many modifications that can be made to this algorithm, and they should be enabled on instantiation such as elitism=true.  The state should not be saved intenerally between optimize calls, this may however been added explicitly."""
    def __init__(self,fitness_fun,gene_spec,debug=0,elitism=True,num_elite=1,culling=True,culling_pct=.2,crossover_prob=.6,mutation_prob=.1,tournament_win_prob=.8,mutation_range_pct=.1,crossover_gene_prob=.3,unique=False):
        self.gene_spec=gene_spec
        self.fitness_fun=fitness_fun
        self.debug=debug
        # Modifications
        self.elitism=elitism
        self.num_elite=num_elite
        self.culling=culling
        self.culling_pct=culling_pct
        self.tournament_win_prob=tournament_win_prob
        self.crossover_prob=crossover_prob
        self.mutation_prob=mutation_prob
        self.mutation_range_pct=mutation_range_pct
        self.crossover_gene_prob=crossover_gene_prob
        self.unique=unique
    def optimize(self,iterations=100,pop_size=100):
        # Create Initial Population
        population=[self.__new_member() for i in range(pop_size)]
        fitness=[]
        # For each generation, evaluate the fitness of the members of the population
        # Create a new population based on selection method
        for generation in range(iterations):
            fitness=map(self.fitness_fun,population)
            if self.debug:
               print('Gen'+str(generation)+ ' - Mean: '+ str(numpy.mean(fitness)) +' Median: ' + str(numpy.median(fitness)) + ' Max: ' + str(max(fitness)) + ' Min: ' + str(min(fitness)))
            if self.debug > 3:
                for i in range(len(fitness)):
                    print('F:'+str(fitness[i])+' Gene:'+str(population[i]))
            population=self.__new_population(pop_size,population,fitness)
        return population[fitness.index(max(fitness))]
    def __new_population(self,pop_size,cur_population,fitness):
        new_population=[]
        sorted_fitness=deepcopy(fitness)
        sorted_fitness.sort()
        if self.culling:
            # Remove the lowest culling_pct % of the population by fitness value
            num_culled=int(max(0,round(self.culling_pct*len(fitness)-1)))
            min_fitness=sorted_fitness[num_culled]
            culled_population=[]
            culled_fitness=[]
            if self.debug > 1:
                print('.:Culling:.')
                print('NumCulled:'+str(num_culled)+'MinFit:'+str(min_fitness))
            # Create new lists of fitness and population that meet or exceed the minimum fitness
            for i in range(len(cur_population)):
                if fitness[i] >= min_fitness:
                    culled_fitness.append(fitness[i])
                    culled_population.append(deepcopy(cur_population[i]))

            # Overwrite the previous values
            cur_population=deepcopy(culled_population)
            fitness=deepcopy(culled_fitness)
            sorted_fitness=deepcopy(fitness)
            sorted_fitness.sort()    

        if self.elitism:
            if self.debug > 1:
                print('.:Elitism:.')
            for elite in range(self.num_elite):
                # Finds the maximum fitness, the index for it, and the parameters that got it, then adds that to the new pop
                new_population.append(deepcopy(cur_population[fitness.index(sorted_fitness[-(elite+1)])]))
                if self.debug > 1:
                    print('Fit:'+str(sorted_fitness[-(elite+1)])+str(new_population[-1]))
        if self.debug > 1:
                print('.:Crossover:.')
        # The following is tournament selection
        for member in range(pop_size-len(new_population)):
            temp_member=deepcopy(cur_population[self.__tournament_battle(fitness)])
            if random.random() < self.crossover_prob: # Multi point crossover
                cross_member=cur_population[self.__tournament_battle(fitness)]
                if self.debug > 1:
                    print("Mem1: "+str(temp_member)+"Mem2: "+str(cross_member))
                for gene in range(len(self.gene_spec)):
                    if random.random() < self.crossover_gene_prob:
                        temp_member[gene]=cross_member[gene]
                if self.debug > 1:
                    print("NewMem: "+str(temp_member))
            # Now we mutate the member
            self.__mutate(temp_member)
            # We test to see if this is a unique member of the new population, if it is not, we force mutation on it
            if self.unique:
                try:
                    new_population.index(temp_member)
                except ValueError:
                    if self.debug > 1:
                        print(".:Unique:.")
                else:
                    if self.debug > 1:
                        print(".:Non-Unique:.")
                    self.__mutate(temp_member,1.0)
            new_population.append(deepcopy(temp_member))
        return new_population
    def __mutate(self,temp_member,mute_prob=None):
        if mute_prob==None:
            mute_prob=self.mutation_prob
        for dim in range(len(temp_member)):
            if random.random() < mute_prob:
                cur_spec=self.gene_spec[dim]
                if type(temp_member[dim])==bool:
                    temp_member[dim]=not temp_member[dim]
                elif type(temp_member[dim])==int or type(temp_member[dim])==long:
                    dim_width=cur_spec[2]-cur_spec[1]
                    delta=(2*dim_width-dim_width)*self.mutation_range_pct*random.random()
                    temp_dim=delta+temp_member[dim]
                    if temp_dim < cur_spec[1]: # Too small
                        temp_dim += dim_width*self.mutation_range_pct
                    elif temp_dim >= cur_spec[2]: # Too large
                        temp_dim -= dim_width*self.mutation_range_pct
                    temp_member[dim]=int(round(temp_dim))
                elif type(temp_member[dim])==float:
                    dim_width=cur_spec[2]-cur_spec[1]
                    delta=(2*dim_width-dim_width)*self.mutation_range_pct*random.random()
                    temp_dim=delta+temp_member[dim]
                    if temp_dim < cur_spec[1]: # Too small
                        temp_dim += dim_width*self.mutation_range_pct
                    elif temp_dim >= cur_spec[2]: # Too large
                        temp_dim -= dim_width*self.mutation_range_pct
                    temp_member[dim]=temp_dim
                else:
                    raise TypeError, "The type specified in the gene is not a bool/int/long/float"
    def __tournament_battle(self,fitness):
        """This picks 2 members randomly and returns the winner of the battle"""
        stronger=random.randrange(0,len(fitness))
        weaker=random.randrange(0,len(fitness))
        if fitness[stronger] < fitness[weaker]: # Ensure stronger is actually stronger or the same
            stronger,weaker=weaker,stronger
        if random.random() > self.tournament_win_prob:
            return weaker # Weaker won
        else:
            return stronger # Stronger won

    def __new_member(self):
        temp_member=[]
        for gene in self.gene_spec:
            if gene[0]==bool:
                temp_member.append(random.random() > .5)
            elif gene[0]==float:
                assert(len(gene)==3)
                temp_member.append((gene[2]-gene[1])*random.random()+gene[1])
            elif gene[0]==int or gene[0]==long:
                assert(len(gene)==3)
                assert((gene[2]-1)>gene[1])
                temp_member.append(int(min(gene[2]-1,max(gene[1],round((gene[2]-gene[1])*random.random()+gene[1])))))
            else:
                 raise TypeError, "The type specified in the gene is not a bool/int/long/float"
        return temp_member
